\section{Ship can stay still}
\label{ShipCanStandStill}
The original problem, where the bomb needs two time units to explode can be extended in such a way, that the ship has also the opportunity to stay still. 
Then there are more possibilities where the ship can be after two steps. 
In the one-restricted graph from figure \ref{GraphN2} for example the ship can be in all the nodes \textit{-2,-1,0,1} or \textit{2} after two steps if 
it can also stay at a node. Therefore, Ferguson's strategy described in section \ref{Strategy2LagShip} has to be extended in such a way that there is also a probability to stay still:
\begin{description}
 \item [p:] Probability to move forwards
\item [s:] Probability to stay still
\item[1-np-s:] Probability to move backwards
\end{description}
The following equations show the probabilities where the ship will be after two steps, if it also has the possibility to stay:
\begin{itemize}
 \item Probability to be at the same point after two steps $P(N_0)=np(1-np-s)+ (1-np-s)^2+s^2 $
 \item Probability to be at any of the $n$ points one step away, not passing the node just visited $P(N_1)=2(ps)$
 \item Probability to be at any of the $n^2$ points two steps away, not passing the node just visited $P(N_2)=p^2$
\item Probability to be at the point one step away, passing the node just visited $P(N_{-1})=2((1-np-s)s)$
\item Probability to be at any of the $n$ points two steps away, passing the node just visited $P(N_{-2})=(1-np-s)p$
\end{itemize}
Table \ref{TableShipStandStill} shows the values for \textit{p} and \textit{s} the ship should use to minimize the maximum of these equations for $n=1,2,3,4$ and 
the corresponding upper bound ($v$) to be hit. 
For comparison, the probabilities to be hit if it cannot stay still are shown in the last column, resulting from the optimal Ferguson strategy 
from section \ref{Strategy2LagShip}. The absolute difference between the maximum hit rate with and without the option to stay still is illustrated on figure \ref{DiagrammVergleichV} for 
$n=1,2,\dots,10$. It can be seen that for bigger $n$, the absolute difference between the two values becomes less. This is because then the ship has more 
possibilities to move and the option to stay still has less impact.

\begin{table}[h]
\begin{center}
  \resizebox{8cm}{!}{
 \begin{tabular}{|c|c|c|c|c|}
\hline
 n & p & s & v & v without staying still \\
\hline
1 & 0.5 & 0.25 & 0.25 & 0.3819 \\
\hline
2 & 0.3542 & 0.1771 & 0.1255 & 0.1716 \\
\hline
3 & 0.2679 & 0.1340 & 0.0718 & 0.0917 \\
\hline
4 & 0.2137 & 0.1069 & 0.0457 & 0.0557\\
\hline
 \end{tabular}}
\caption{$p$, $s$ and hit rate, two-move lag with staying still }
\label{TableShipStandStill}
\end{center}
\end{table}

\begin{figure}[h]
 \begin{center}
  \includegraphics[width=3.6in]{Bilder/CompareVWithandWithoutStandStill}
\caption{Comparison of value $v$ with and without option to stay still}
 \end{center}
\label{DiagrammVergleichV}
\end{figure}

To ensure that $v$ really is the upper bound, like in Ferguson's strategy, it has to be checked that for the very first step the probability where the ship will be after the very first two steps is less or equal than the upper bound $v$ from table \ref{TableShipStandStill}. This is only the case when the ship moves in the first step, hence it is forced to move in this first step. Then the probabilities are as follows:
\begin{itemize}
 \item Probability to be back at the starting point after the first two steps $P(N_{S})= 1-np-s$
 \item Probability to be one step away from the starting point after the first two steps $P(N_{S1})=\frac{s}{n+1}$
 \item Probability to be two steps away from the starting point after the first two steps $P(N_{S2})=\frac{p}{n+1}$
\end{itemize}



